In a communication system, channel coding is usually adopted to improve data transmission reliability and ensure communication quality. Polar codes are a coding mode that can achieve the Shannon capacity and have low coding and decoding complexity. The Polar codes are a type of linear block codes. A generator matrix thereof is GN., and a coding process thereof is x1N=u1NGN., where GN.=BNF{circle around (×)}n, a code length N=2n, and n≧0.
      F    =          [                                    1                                0                                                1                                1                              ]        ,and BN is a transposed matrix, such as a bit reversal matrix.
F{circle around (×)}n is a Kronecker power of the F, and is defined as F{circle around (×)}n=F{circle around (×)}F{circle around (×)}(n-1). The Polar codes can be expressed as (N, K, A, uAc) by using a coset code, and a coding process thereof is x1N=uAGN.(A)⊕uAcGN.(AC), where A is a set of an information bit index, GN. (A) is a submatrix of GN. formed by the rows with indexes in the set A, and GN. (AC) is a submatrix of GN. formed by the rows with indexes in the set AC. uAc represents frozen bits, the number thereof being (N−K), and are known bits. For simplicity, these frozen bits may be set to be 0.
SC (successive-cancellation) decoding may be adopted for decoding the Polar codes, and the process thereof is as follows:
Considering a type of Polar codes, and parameters thereof are (N, K, A, uAc).
In the SC decoding, the following conditional likelihood functions are calculated in sequence:
                                          L            N                          (              i              )                                ⁡                      (                                          y                1                N                            ,                                                u                  ^                                1                                  i                  -                  1                                                      )                          ⁢                  =          Δ                ⁢                                            W              N                              (                i                )                                      ⁡                          (                                                y                  1                  N                                ,                                                                            u                      ^                                        1                                          i                      -                      1                                                        |                  0                                            )                                                          W              N                              (                i                )                                      ⁡                          (                                                y                  1                  N                                ,                                                                            u                      ^                                        1                                          i                      -                      1                                                        |                  1                                            )                                                          (        1        )            
y1N is a received signal vector (y1, y2, . . . , yN), and u1i-1 is a bit vector (u1, u2, . . . , ui-1). W is a transition probability, and L denotes a log-likelihood ratio.
If i⊂A, judgment is as follows:
                                          u            ^                    i                =                  {                                                                      0                  ,                                                                                                  if                    ⁢                                                                                  ⁢                                                                  L                        N                                                  (                          i                          )                                                                    ⁡                                              (                                                                              y                            1                            N                                                    ,                                                                                    u                              ^                                                        1                                                          i                              -                              1                                                                                                      )                                                                              ≥                  1                                                                                                      1                  ,                                                            others                                                                        (        2        )            If i⊂AC, simply let {circumflex over (u)}i=ui  (3)
In the above formulas (2) and (3), ûi denotes a judgment value of the bit ui.
Complexity of the SC decoding is O(N log2 N). The SC decoding may achieve good performance and approach the Shannon limit in a situation that the code length N is very long. However, when N is quite short or in a moderate length, performance of the Polar codes with the SC decoding is not superior to performance of Turbo codes and LDPC (Low-density Parity-check, low-density parity-check) codes, and the decoding performance needs to be further improved.
The SC decoding is performed in order of bits, and each decoded bit is used for subsequent bit decoding after hard judgment. In this way, error propagation may exist, resulting in degradation of decoding performance. List (list) decoding maintains multiple candidate paths, and can achieve decoding performance approaching the maximum likelihood. SC-List decoding is obtained by combining the SC decoding and the List decoding.
Complexity of the current SC-List decoding is O (L×N×log2 N), about L times of complexity of the SC decoding, which is relatively higher. Therefore, the List decoding complexity of the Polar codes needs to be reduced.